#257.二叉树的所有路径
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[str]
        """
        result = []
        if root is None:
            return result

        def dfs(node, path):
            # 如果路径不为空，添加 "->" 分隔符
            if path:
                path += "->"
            # 将当前节点的值添加到路径中
            path += str(node.val)

            # 如果是叶子节点，将路径添加到结果列表
            if node.left is None and node.right is None:
                result.append(path)
                return

            # 递归遍历左子树
            if node.left:
                dfs(node.left, path)
            # 递归遍历右子树
            if node.right:
                dfs(node.right, path)
        # 从根节点开始深度优先搜索
        dfs(root, "")
        return result
'''



# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def binaryTreePaths(self, root: 'Optional[TreeNode]') -> 'List[str]':
        """
        获取二叉树的所有路径，并以字符串形式返回。

        :param root: 二叉树的根节点
        :type root: Optional[TreeNode]
        :return: 包含所有路径的列表
        :rtype: List[str]
        """
        result = []

        def dfs(node, path):
            if not node:
                return

            # 将当前节点的值添加到路径中
            if path:
                path += f"->{node.val}"
            else:
                path = str(node.val)

            # 如果是叶子节点，将路径添加到结果列表
            if not node.left and not node.right:
                result.append(path)
                return

            # 递归遍历左子树
            if node.left:
                dfs(node.left, path)
            # 递归遍历右子树
            if node.right:
                dfs(node.right, path)

        # 从根节点开始深度优先搜索
        dfs(root, "")
        return result

if __name__ == "__main__":
    # 构建一个简单的二叉树
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.right = TreeNode(5)

    solution = Solution()
    paths = solution.binaryTreePaths(root)
    print(paths)
